package com.zwj.interview.链表;

/**
 * @Author: Zwj
 * @Date: 2023/2/13 11:05
 */
public class 链表奇偶数重排 {

    public ListNode oddEvenList(ListNode head) {
        // write code here
        if (head == null || head.next == null) {
            return head;
        }
        //偶数节点的头节点
        ListNode evenHead = head.next;
        //奇数节点的头结点
        ListNode odd = head;
        ListNode even = head.next;
        while (even != null && even.next != null) {
            //odd连接even的后一个，即奇数位
            odd.next=even.next;
            //odd进入后一个奇数位
            odd=odd.next;
            //even连接后一个奇数的后一位，即偶数位
            even.next=odd.next;
            //even进入后一个偶数位
            even=even.next;
        }
        odd.next = evenHead;
        return head;
    }
}